/*
	二分查找:对有序数组
 */

//递归查找
function binary_search(array, val) {
    if (!array) return -1;
    var len = array.length;
    if (len === 0) return -1;
    var mid = Math.floor(len / 2);
    if (array[mid] === val) {
        return mid;
    } else if (array[mid] > val) {
        index = binary_search(array.slice(0, mid), val);
        return index == -1 ? -1 : index;

    } else {
        index = binary_search(array.slice(mid + 1, len), val);
        return index == -1 ? -1 : mid + 1 + index;
    }

}


// 非递归查找
function binary_find(array, val) {
    if (!array) return -1;
    var len = array.length;
    var start = 0,
        end = len - 1;
    while (start <= end) {
        var mid = Math.floor((start + end) / 2);
        if (array[mid] === val) {
            return mid;
        } else if (array[mid] > val) {
            end = mid - 1;
        } else if (array[mid] < val) {
            start = mid + 1;
        }
    }
    return -1;
}


var arr = [23, 44, 51, 59, 63, 71, 75, 88, 97, 101];

console.log(binary_search(arr, 59));
console.log(binary_find(arr, 171));